
/*
记忆化搜索
连接:https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/
题目:375. 猜数字大小 II
 

   
*/

///记忆化搜索
class Solution {
public:
    int memo[201][201];
    int getMoneyAmount(int n) {
        return dfs(1,n);
    }
    int dfs(int left,int right)
    {
        if(left>=right) return 0;//两种情况，无效区间，区间只有一个数是叶子节点
        if(memo[left][right]!=0)
            return memo[left][right];
        int ret = INT_MAX;
        for(int head = left;head<=right;head++)
        {
            int x = dfs(left,head-1);
            int y = dfs(head+1,right);
            ret = min(ret,head+max(x,y));
        }
        memo[left][right] = ret;
        return ret;
    }
};